Complex Brain Networks: A Graph-Theoretical Analysis

235

9.4.2

Modules in Brain Networks

Discovery of dense regions in brain networks may provide insight into un-

derstanding basic brain functions related to its topology [8]. These highly

connected regions perform specialized functions cooperating and coordinating

with each other to produce high-level cognitive tasks. Since detection of mod-

ules is an NP-hard problem with no algorithmic solutions in polynomial time,

heuristics are commonly used.

Modularity maximization is widely used to find modules in brain networks

due to its fast convergence and efficient use in large networks. A heuristic called

Louvian heuristic is used in [9] to provide a fast modularity maximization in

large networks. Each node is a cluster initially and moving nodes between

clusters is evaluated in terms of modularity gains achieved. The authors report

that the quality of the communities discovered using their method is very good

with fast computation time.

Dynamic community structure in multilayer networks is considered in [10]

by analysing the behavior of several null models used for optimizing quality

functions such as modularity. Although modularity maximization proves to

be a favourable heuristic to detect communities in networks, it is difficult to

use it directly to find clusters in hierarchical networks making it unsuitable

to find these dense regions in brain networks. A weighted modularity maxi-

mization(WMM) method that uses the weighted adjacency matrix is proposed

in [11] to be used in functional brain networks to overcome the difficulties of

applying the modularity maximization method directly in these networks. The

authors present a two-step maximization method to detect hierarchical clus-

ters in functional brain networks by testing hierarchy of the clusters using node

attributes. Various clustering methods applied to neuroimaging data to dis-

cover clusters in brain networks include spectral clustering [12] and bayesian

community detection [13].

9.5

Motifs of the Brain

A network motif is a frequently found subnetwork of a given brain network.

Such a repeating structure may indicate some basic function performed by

that motif. Moreover, detection of similar motifs in various BFNs may indicate

similarity which may be useful in the diagnose of diseases.

9.5.1

Background

Discovery of a subgraph within a larger graph is an NP-Hard problem, thus,

approximation algorithms or more commonly, heuristic algorithms are needed.

Some common directed network motifs of three nodes found in brain networks